/*
 * @lc app=leetcode.cn id=472 lang=typescript
 *
 * [472] 连接词
 */

// @lc code=start

class TrieNode {
  isWord: boolean = false;
  children: TrieNode[] = new Array(26);
}

class Trie {
  base: number = 97;
  root: TrieNode = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      const index = word.charCodeAt(i) - this.base;
      if (node.children[index] === void 0) {
        node.children[index] = new TrieNode();
      }
      node = node.children[index];
    }
    node.isWord = true;
  }
}

function findAllConcatenatedWordsInADict(words: string[]): string[] {
  // 将 words 通过长度升序排序
  words.sort((a, b) => a.length - b.length);

  const dfs = (word: string, start: number, tire: Trie): boolean => {
    const n = word.length;
    // 找到结尾了
    if (n === start) return true;

    let node: TrieNode = tire.root;
    for (let i = start; i < n; i++) {
      const index = word.charCodeAt(i) - tire.base;
      node = node.children[index];
      // 字典树中未找到有效结果
      if (node === void 0) return false;
      // 找到结果，继续匹配后续的字符串是否可以找到
      if (node.isWord) {
        if (dfs(word, i + 1, tire)) return true;
      }
    }
    return false;
  };

  const tire = new Trie();
  const ans: string[] = [];
  // 遍历 words ，处理每一个单词
  for (const word of words) {
    if (word === '') continue;
    if (dfs(word, 0, tire)) {
      // 如果能找到较短单词组成，当前元素放入答案
      ans.push(word);
    } else {
      // 否则放入字典树中当做短语
      tire.insert(word);
    }
  }

  return ans;
}
// @lc code=end
